// m

// 给定一个单链表的头节点的head
// 要求将链表中的奇数位置上的节点排在前面，偶数位置上的节点排在后面，返回新的链表节点

// 要求空间复杂度为O(1)

// 思路：  先将奇数位置上的节点和偶数位置上的节点分成两个链表，再将偶数节点的链表接到奇数链表的末尾
// 过程中需要使用几个必要指针用于保留必要位置（比如原链表初始位置，偶数链表初始位置，当前遍历节点位置）
const { ListNode, LinkedList } = require('../../1. 链表基础/1. 建立线性链表')

function oddEvenList(head) {
    // 少于三个节点
    if (!head || !head.next || !head.next.next) {
        return head
    }
    let evenHead = head.next
    // 指向奇数节点链表
    let odd = head
    // 指向偶数节点链表
    let even = evenHead
    let isOdd = true

    let curr = head.next.next

    while (curr) {
        if (isOdd) {
            odd.next = curr
            odd = curr
        } else {
            even.next = curr
            even = curr
        }
        isOdd = !isOdd
        curr = curr.next
    }
    odd.next = evenHead
    even.next = null
    return head
}
let head = [1, 2, 3, 4, 5]
let node = new LinkedList(head)
console.log(oddEvenList(node.head))
